import java.util.Arrays;
import java.util.Vector;


public class arrayTree {
	int numNodes = 0;
	binaryOps bop = new binaryOps(4);
	int maxPathSize = 32;
	int quickCodes[]; //index is code, val is aftercode;
	fastSparseArray decompQuickCodes;
	TreeNode rootNode;
	Vector<Integer> leafs = new Vector<Integer>();
	fastSparseArray dataArray; // 0 is code, 1 is afterCode; afterCode has leading 1!!
	fastSparseArray nodeExists;
	arrayTree(TreeNode r) {
		rootNode = r;
	}
	void setRoot(TreeNode a) { rootNode = a; };
	
	void buildArray() {
		int arsz = findArraySize();
		System.out.println("Trying this size: " + arsz);
		dataArray = new fastSparseArray<int[]>(0,arsz,100000);
		nodeExists = new fastSparseArray<Boolean>(0,arsz,100000);
		System.out.println("Setup memory structures with arsz: " + arsz);
		int emptyVal[] = new int[2];
		emptyVal[0] = 0;
		emptyVal[1] = 0;
		bop.startTimer("Zero'ing out dataArray took...");
		dataArray.setDefaultValue(emptyVal);
		nodeExists.setDefaultValue(Boolean.FALSE);
		
		bop.endTimer();
		boolean pathVar[] = new boolean[maxPathSize];
		for(int i=0; i < maxPathSize; i++) {
			pathVar[i] = false;
		}
		bop.startTimer("Building array Recursively took..");
		buildArrayRec(rootNode,0,pathVar,0);
		bop.endTimer();
		System.out.println("There exists this many nodes in the tree: " + numNodes);
		//System.out.println("The size of the data array is: " + dataArray.length);
		//printTree();
		bop.startTimer("Setting up quick codes array");
		setupQuickCodes();
		bop.endTimer();
	}
	void buildArrayFromCodeTable(int codeTable[][]) {
		bop.startTimer("Building array from code table read from file");
		int arSize = findArraySizeFromCodeTable(codeTable);
		dataArray = new fastSparseArray<int[]>(0,arSize,100000);
		nodeExists = new fastSparseArray<Boolean>(0,arSize,100000);
		decompQuickCodes = new fastSparseArray<Integer>(0,100000,60000);
		int empty[] = new int[2];
		empty[0] = 0;
		empty[1] = 0;
		boolean path[];
		int cPos = 0;
		
		dataArray.setDefaultValue(empty);
		nodeExists.setDefaultValue(Boolean.FALSE);
		decompQuickCodes.setDefaultValue(0);	
		for(int i=0; i < codeTable.length; i++) {
			decompQuickCodes.add(codeTable[i][1], codeTable[i][0]);
			cPos = 0;
			path = bop.booleanFromInteger(codeTable[i][1]);
			nodeExists.add(cPos, true);
			for(int m=1; m < path.length; m++) { //skip first 1
				if(path[m]) {
					cPos = right(cPos);
					nodeExists.add(cPos, true);
				}
				if(!path[m]) {
					cPos = left(cPos);
					nodeExists.add(cPos, true);
				}
			}
			nodeExists.add(cPos, true);
			int tempVar[] = codeTable[i];
			dataArray.add(cPos, tempVar);
		}
		bop.endTimer(); 
	}
	
	int getDecompQuickCode(int aftCode) {
		boolean[] qcode = bop.booleanAddLeading1(bop.booleanFromInteger(aftCode));
		return (Integer)decompQuickCodes.get(bop.integerFromBooleans(qcode));
	}
	int numLeafs() { return leafs.size(); };
	int[] getLeaf(int num) { 
		if(!exists(leafs.get(num))) {
			System.out.println("Error getting a leaf that doesn't exis, leaf num: " + num);
			return null;
		}
		return (int[])dataArray.get(leafs.get(num));
	}
	void buildArrayRec(TreeNode cNode,int pos,boolean path[],int pathPos) {
		int tempVal[] = new int[2];
		tempVal[0] = cNode.code;
		
		if(cNode.isLeaf) {	
			cNode.booleanBitCode = buildPath(path,pathPos);
			cNode.afterCode = (bop.integerFromBooleans(bop.booleanAddLeading1(cNode.booleanBitCode)));
			 //will have leading 1, to preserve leading integers
		}
		tempVal[1] = cNode.afterCode;
		dataArray.add(pos, tempVal);
		if((Boolean)nodeExists.get(pos)== null) numNodes++;
		else if(((Boolean)nodeExists.get(pos)== false))numNodes++;
		nodeExists.add(pos, true);
		
		if(cNode.left != null) {
			path[pathPos] = false;
			buildArrayRec(cNode.left,(2*pos) + 1,path,pathPos+1);
		}
		if(cNode.right != null) {
			path[pathPos] = true;
			buildArrayRec(cNode.right,(2*pos) + 2,path,pathPos+1);
		}
		if(isLeaf(pos)) leafs.add(pos);
	}
	boolean[] buildPath(boolean path[], int pathPos) {
		int plen = pathPos;
		if(plen == 0) return null;
		boolean tempPlace[] = new boolean[plen];
		for(int i=0; i < plen; i++) {
			tempPlace[i] = path[i]; 
		}
		return tempPlace;
	}
	boolean afterCodeIsGood(boolean[] in) {
		int cPos = 0;
		for(int m=1; m < in.length; m++) { //skip first 1
			if(in[m]) cPos = right(cPos);
			if(!in[m]) cPos = left(cPos);
		}
		return isLeaf(cPos);
	}
	boolean[] getBooleanCodeFromAfterCode(boolean[] in) {
		return bop.booleanFromInteger(getCodeFromAfterCode(bop.integerFromBooleans(in)));
	}
	int getCodeFromAfterCode(int tp) {
		int retval = 0;
		int curPos = 0;
		boolean path[] = bop.booleanFromInteger(tp);
		int tv[] = new int[2];
		for(int i=1; i < path.length; i++) {
			
			if(!path[i]) {
				if(!hasLeft(curPos)) System.out.println("Error in getting code from after code, " + curPos + " has no left,but wants one");
				curPos = left(curPos);
				tv = (int[])dataArray.get(curPos);
			}
			if(path[i]) {
				if(!hasRight(curPos)) System.out.println("Error in getting code from after code, " + curPos + " has no right,but wants one");
				curPos = right(curPos);
				tv = (int[])dataArray.get(curPos);
			}
			tv = (int[])dataArray.get(curPos);
			if(!isLeaf(curPos) && tv[1] != 0) System.out.println("Error: Is a leaf with afterCode at " + curPos);
		}
		tv = (int[])dataArray.get(curPos);
		int a = tv[0];
		return tv[0];
		
	}
	boolean[] getCodeFromAfterCodeInBinary(int afterC) { return bop.booleanFromInteger((getCodeFromAfterCode(afterC))); };
	int getAfterCodeFromCode(int code) {
		int tv[] = new int[2];
		for(int i=0; i < leafs.size(); i++) {
			tv = (int[])dataArray.get(leafs.get(i));
			if(code == tv[0]) return tv[1];
		}
		System.out.println("Erorr: Failed to get after code from code: " + code);
		return 0;
	}
	int quickGetAfterCodeFromCode(int code) {
		return 	quickCodes[code];
	}
	
	void setupQuickCodes() {
		int tv[] = new int[2];
		int greatestCode = 0;
		for(int i=0; i < leafs.size(); i++) {
			tv = (int[])dataArray.get(leafs.get(i));
			if(tv[0] > greatestCode) greatestCode = tv[0];
		}
		quickCodes = new int[greatestCode+1];
		for(int i=0; i < leafs.size(); i++) {
			tv = (int[])dataArray.get(leafs.get(i));
			quickCodes[tv[0]] = tv[1];
		}
		//Arrays.sort(quickCodes);
	}
	boolean[] getAfterCodeFromCodeInBinary(int c) { return bop.booleanFromInteger((getAfterCodeFromCode(c))); };
	

	boolean checkInBounds(int pos) {
		if(pos >= dataArray.length()) return false;
		return true;
	}
	boolean isLeaf(int pos) {
		if(!exists(left(pos)) && !exists(right(pos))) return true;
		return false;
	}
	boolean hasLeft(int pos) {
		return exists(left(pos));
	}
	boolean hasRight(int pos) {
		return exists(right(pos));
	}
	boolean exists(int pos) {
		if (checkInBounds(pos)) {
			return (Boolean)nodeExists.get(pos);
		}
		return false;
	}
	int left(int pos) { return (2*pos) +1; };
	int right(int pos) { return (2*pos) + 2; };
	int findArraySizeFromCodeTable(int codeTable[][]) {
		int maxAfterCode = 1;
		for(int i=0; i < codeTable.length; i++) {
			if(codeTable[i][1] > maxAfterCode) maxAfterCode = codeTable[i][1];
		}
		int height = (bop.booleanFromInteger(maxAfterCode).length) - 1;
		int retval = 1;
		retval = retval << (height + 1);
		return retval;
	}
	int findArraySize() {
		int height = findDeepest(rootNode);
		System.out.println("The max height of any leaf is: " + height);
		if(height > 23) System.out.println("WARNING: MOST SYSTEMS CANNOT HANDLE SUCH A LARGE TREE, YOU MAY GET A java HEAP failure");
		int retval = 1;
		retval = retval << height + 1;
		retval = retval - 1;
		return retval;
	}
	int findDeepest(TreeNode cNode) {
		int retval1 = 0;
		int retval2 = 0;
		if(cNode.left != null) retval1 = findDeepest(cNode.left);
		if(cNode.right != null) retval2 = findDeepest(cNode.right);
		if(retval1 > retval2) return retval1 + 1;
		return retval2 + 1;
	}
	char printArray[][];
	int colCount = 0;
	void printTree() {
		int level = findDeepest(rootNode);
		updatePrintTree(rootNode,0,0);
		printArray = new char[level*2][numNodes * 2];
		for (int i = 0; i < level * 2; i++) {
			for (int j = 0; j < numNodes * 2; j++) {
				printArray[i][j] = ' ';
			}
		}
		printTree(rootNode);
		dumpTree(level,colCount);
	}
	
	void updatePrintTree(TreeNode cNode,int column, int level) {
		if(cNode.left == null && cNode.right == null) {
			cNode.level = level;
			cNode.column = column;
			colCount++;
			return;
		}
		if(cNode.left != null)updatePrintTree(cNode.left,colCount,level+1);
		cNode.level = level;
		cNode.column = colCount;
		colCount++;
		if(cNode.right != null)updatePrintTree(cNode.right,colCount,level+1);
	
	}
	void printTree(TreeNode cNode) {
		
		if(cNode.isLeaf()) printArray[cNode.level * 2][cNode.column * 2] = 'L';
		else printArray[cNode.level * 2][cNode.column * 2] = 'n';
		if (cNode.left != null) {
			final int colDif = cNode.column - cNode.left.column;
			printTree(cNode.left);
			if (colDif > 0) {
				printArray[(cNode.level * 2) + 1][(cNode.column * 2)] = '^';
				for (int i = 1; i < (colDif * 2); i++) {
					printArray[(cNode.level * 2) + 1][(cNode.column * 2) - i] = '-';
				}
			}
			printArray[(cNode.level * 2) + 1][(cNode.column * 2) - (colDif * 2)] = '/';
		}
		if (cNode.right != null) {
			printTree(cNode.right);
			final int colDif = cNode.right.column - cNode.column;
			if (colDif > 0) {
				printArray[(cNode.level * 2) + 1][(cNode.column * 2)] = '^';
				for (int i = 1; i < (colDif * 2); i++) {
					printArray[(cNode.level * 2) + 1][(cNode.column * 2) + i] = '-';
				}
			}
			printArray[(cNode.level * 2) + 1][(cNode.column * 2) + ((colDif * 2))] = '\\';
		}
	}
	void dumpTree(int maxLevels, int maxColumns) {
		for (int i = 0; i < maxLevels * 2; i++) {
			for (int j = 0; j < maxColumns * 2; j++) {
				System.out.print(printArray[i][j] + "  ");
			}
			System.out.println();
		}
	}
}
